they SB-tree paper also goes way way out of its way to shout out a completely different paper describing a "BD-tree" ("bounded decision") data structure, just because they really like it???? so wholesome!!!!
The common uses of merge join and ordered user display seem to require the more difficult key sequential access, although Lomet points out that for many uses. "By changing algorithms, it is frequently possible to use the results of a range search, without the extra cost of putting the records in key order." To support key sequential access, BD file records within each bucket are maintained in key order. Since records are ordered from one node to another, a total ordering can be achieved by performing a "merge" on the ordered sequences from the different buckets of a node, as in the final stage of a multi-merge sort. This is best effected by using a "heap" structure on the smallest keys in each bucket, successively removing the minimum, inserting the next in that bucket, and reorganizing the heap; each such heap reorganization takes log_2 k steps, where k is the number of buckets.
basically the moral of all of the good papers is: don't rely on one single algorithm or data structure to generally work fine across every possible use case! develop algorithms and data structures tuned to each potential query and input distribution you expect to have to handle!!
